package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.sun.corba.se.impl.orbutil.graph.Node;
import com.sun.javafx.image.IntPixelAccessor;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.datastructure.ListNode;

/*
 * 
 原题　
		Follow up for "Unique Paths":
	
	Now consider if some obstacles are added to the grids. How many unique paths would there be?
	
	An obstacle and empty space is marked as 1 and 0 respectively in the grid.
	
	For example,
	
	There is one obstacle in the middle of a 3x3 grid as illustrated below.
	
	[
	  [0,0,0],
	  [0,1,0],
	  [0,0,0]
	]

 题目大意

 解题思路
 	与 @_063_Unique_Paths_II一样，只是假如遇到障碍点obstacleGrid[i][j]，就直接设置改点为0 dp[i][j]=0

 @Type 动态规划
 * @Date 2017-10-02 23:37
 */
public class _063_Unique_Paths_II {

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid == null || obstacleGrid.length==0 || obstacleGrid[0].length==0)  
            return 0;  
    	int m = obstacleGrid.length, n = obstacleGrid[0].length;

		int[][] dp = new int[m][n];
		

	
		/**
		 * 		eg：[1][1]为障碍物，即：obstacleGrid[1][1]=1
		 * 				那么到[2][1]([1][1]下方的点), 的方案只有一种：从[2][0]向右走一格
		 * 			状态转换式依然为: dp[2][1] = [1][1] + dp[2][0];		//但：此时[1][1]为0
		 */
		dp[0][0] = 1;

		
    	for (int i = 0; i < m; i ++) {
			for (int j = 0; j < n; j ++) {
				if (obstacleGrid[i][j] == 1) {
					dp[i][j] = 0;
				} else {
					if (i-1 >= 0) {
						dp[i][j] += dp[i-1][j];
					}
					if (j-1 >= 0) {
						dp[i][j] += dp[i][j-1];
					}
				}
			}
		}
		return dp[m-1][n-1];
    }

	public static void main(String[] args) {
		_063_Unique_Paths_II obj = new _063_Unique_Paths_II();

		ListNode list = ListNode.newLinkList2();
		LogUtils.print(obj.uniquePathsWithObstacles(new int[][] 
				{
					{0, 0},
					{1, 0}
				
				}
		));

		// ListNode.traverse("remove", list);
	}

}
